/*
 * @Author: scl
 * @Date: 2023-09-07 21:22:21
 * @LastEditTime: 2023-09-08 22:59:45
 * @Description: file content
 */
/*
 * @lc app=leetcode.cn id=90 lang=typescript
 *
 * [90] 子集 II
 *
 * https://leetcode.cn/problems/subsets-ii/description/
 *
 * algorithms
 * Medium (63.55%)
 * Likes:    1148
 * Dislikes: 0
 * Total Accepted:    321.2K
 * Total Submissions: 505.3K
 * Testcase Example:  '[1,2,2]'
 *
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 * 
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 * 
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [1,2,2]
 * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [0]
 * 输出：[[],[0]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * -10 
 * 
 * 
 * 
 * 
 */

// @lc code=start
function subsetsWithDup(nums: number[]): number[][] {
    nums.sort(function (a, b) { return a - b; });
    const ans = [[]], len = nums.length, arr = [];
    let n = 1;
    while (n <= len) {
        dfs(0, n);
        n++
    }
    return ans;
    function dfs(index, n) {
        if (arr.length == n) {
            if (!arrIsInArrs(ans, arr))
                ans.push([...arr]);
            return;
        }
        for (let i = index; i <= len - n+arr.length; i++) {
            if(arr.length==0&&i!=0&&nums[i]==nums[i-1])continue
            arr.push(nums[i]);
            dfs(i + 1, n);
            arr.pop();
        }
    }
    function arrIsInArrs(arrs, arr) {
        let index=arrs.length-1
        const len1=arr.length
        while(index>=0){
            let len2=arrs[index].length
            if(len2!=len1)break
            if(compareTwoArr(arrs[index],arr,len1))return true
            index--
        }
        return false;
    }
    
    function compareTwoArr(arr1,arr2,len){
        //前提条件长度相同
        for(let i=0;i<len;i++)
            if(arr1[i]!=arr2[i])return false
        return true
    }
};
// @lc code=end

